package practice_2025_8_8;

class Solution {
    /**
     * 解码方法
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        int len = s.length();
        // dp[i]: 以 i 为结尾, 共 dp[i] 种解码方法
        // str[i] -> dp[i - 1]
        // str[i - 1] + str[i] -> dp[i - 2]
        int[] dp = new int[len];
        // 初始化
        int num = s.charAt(0) - '0';
        if (num <= 0) {
            return 0;
        }
        dp[0] = 1;
        if (len <= 1) {
            return dp[0];
        }
        num = num * 10 + (s.charAt(1) - '0');
        if (num >= 10 && num <= 26) {
            dp[1] = 1 + dp[0];
        }
        for(int i = 2; i < len; i++) {
            int k = s.charAt(i) - '0';
            if (k > 0) {
                dp[i] += dp[i - 1];
            }
            k = k + (s.charAt(i - 1) - '0') * 10;
            if (k >= 10 && k <= 26) {
                dp[i] += dp[i - 2];
            } 
        }
      //  System.out.println(Arrays.toString(dp));
        return dp[len - 1];
    }

    /**
     * 买卖股票的最佳时机III
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // pr[i]: 第i 天股票的价格
        // 最多完成两笔交易
        // 未购入 ->（-pr[i]） 已购入未卖出 -> 未购入(+pr[i])
        int len = prices.length;
        if (len <= 1) return 0;
        int k = 2;
        int[][] f = new int[len][k]; // 已购入未卖出
        int[][] g = new int[len][k]; // 未购入
        int init = -0xffff;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < k; j++) {
                f[i][j] = init;
                g[i][j] = init;
            }
        }
        f[0][0] = -prices[0];
        int max = 0;
        for(int i = 1; i < len; i++) {
            // f[i][j] = Math.max(f[i - 1][j], g[i - 1][j - 1] - prices[i]); // 当前买入未卖出
            // g[i][j] = Math.max(g[i - 1][j], f[i - 1][j] + prices[i]); // 当前售出
            for(int j = 0; j < k; j++) {
                // 第一笔
                if (j == 0) {
                    f[i][0] = Math.max(f[i - 1][0], -prices[i]);
                    g[i][0] = Math.max(g[i - 1][0], f[i - 1][0] + prices[i]);
                } else {
                    // 第 j 笔, j - 1笔已经卖出
                    if (g[i - 1][j - 1] >= init) {
                        f[i][j] = Math.max(f[i - 1][j], g[i - 1][j - 1] - prices[i]);
                    }
                    // 第 j 笔卖出 -> 第 j 笔已经买入
                    if (f[i - 1][j] >= init) {
                        g[i][j] = Math.max(g[i - 1][j], f[i - 1][j] + prices[i]);
                    }
                }
            }
        }
        return Math.max(Math.max(g[len - 1][0], g[len - 1][1]), 0);
    }

    /**
     * 环绕字符串中的唯一字符串
     * 记得去重
     * @param s
     * @return
     */
    public int findSubstringInWraproundString(String s) {
        String bash = "zabcdefghijklmnopqrstuvwxyz";
        int len = s.length();
        // dp[i]: 以 i 为结尾的字符串，非空子串的个数
        int count = 0;
        int[] dp = new int[len];
        int[] chs = new int[26];
        for(int i = 0; i < len; i++) {
            dp[i] = 1;
        }
        int index = s.charAt(0) - 'a';
        chs[index] = 1;
        for(int i = 1; i < len; i++) {
            index = s.charAt(i) - 'a';
            if (s.charAt(i - 1) == bash.charAt(index)) {
                dp[i] += dp[i - 1];
            }
            chs[index] = Math.max(chs[index], dp[i]);
        }
//        System.out.println(Arrays.toString(chs));
        for(int i = 0; i < 26; i++) {
            count += chs[i];
        }
        return count;
    }

    /**
     * 最长公共子序列
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j]: 以 test1 i 位置结尾, test2 j 位置结尾的最长长度
        int len1 = text1.length();
        int len2 = text2.length();
        text1 = " " + text1;
        text2 = " " + text2;
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }

    /**
     * 目标和
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        // 可添加 + 或 -
        // 串联所有, 构成一个表达式, 表达式结果为 target
        // 当前位置: + 或 -
        // 选择+的和为 a, 选择 - 的和为b
        // a + b = sum
        // a - b = target
        // a = (sum + target) / 2; a 必须为整数且大于等于0
        // dp[i][j]: 前 i 个元素中选择, 使得和恰好为j的表达式数目
        // 可以选: j - nums[i] >= 0
        // 且 dp[i - 1][j - nums[i]] > 0 -> max()
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int a = (sum + target) / 2;
        if ((sum + target) % 2 != 0 || a < 0) {
            return 0;
        }
        // 滚动数组优化
        int[] dp = new int[a + 1];
        // 初始化
        dp[0] = 1;
        //int count = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = a; j >= 0; j--) {
                if (j - nums[i] >= 0) {
                    dp[j] += dp[j - nums[i]];
                }
            }
            //    System.out.println(Arrays.toString(dp));
        }
        return dp[a];
    }

    /**
     * 最后一块石头的重量
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        // 剩下的要最小 -> sum / 2 最好
        // 分成两部分：大 - 小 = 剩下的
        int sum = 0;
        for(int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        // dp[i][j]: 从前 i 个中选, 总重量不超过 j, 此时的最大重量
        // j - stones[i] >= 0 -> dp[i][j] = max(dp[i - 1][j - s[i]] + s[i], dp[i - 1][j])
        int[] dp = new int[target + 1];
        for(int i = 0; i < stones.length; i++) {
            for(int j = target; j >= 0; j--) {
                if (j - stones[i] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
            //     System.out.println(Arrays.toString(dp) + " " + sum);
        }
        return sum - dp[target] * 2;
    }

    /**
     * 完全平方数
     * @param n
     * @return
     */
    public int numSquares(int n) {
        // 返回和为 n 的完全平方数的最少数量
        // 总和必须为 n -> 装满
        // dp[i][j]: 从前 i 个中选, 平方和为 j 的最小数量
        // j - i*i*i >= 0 & dp[j - i*i*i] > 0
        // dp[i][j] = min(dp[j - k * (i^3)])
        // dp[i][j - i^3] = min()
        // dp[i][j] = min(dp[i - 1][j], dp[i][j - i^3] + 1)
        int k = (int)Math.sqrt(n) + 1;
        int[] dp = new int[n + 1];
        // 初始化
        int max = 0xffff;
        for(int i = 0; i <= n; i++) {
            dp[i] = max;
        }
        dp[0] = 0;
        for(int i = 1; i <= k; i++) {
            for(int j = 0; j <= n; j++) {
                int psqu = i * i;
                if (j - psqu >= 0 && dp[j - psqu] < max) {
                    dp[j] = Math.min(dp[j], dp[j - psqu] + 1);
                }
            }
            //      System.out.println(Arrays.toString(dp) + " " + k);
        }
        return dp[n];
    }

    /**
     * 一和零
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        // 0 的个数 < m
        // 1 的个数 < n
        // dp[i][j][k]: 从前 i 个中选, 0的个数小于M,1的个数小于n,此时的最大子集长度
        // 统计当前的01个数: 0: a, 1: b
        // 满足: m - a >= 0 && n - b >= 0
        // dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a][n - b] + 1)
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for(int i = 0; i < strs.length; i++) {
            int[] tmp = count(strs[i]);
            int zeroCount = tmp[0];
            int oneCount = tmp[1];
            for(int j = m; j >= 0; j--) {
                for(int k = n; k >= 0; k--) {
                    if (j - zeroCount >= 0 && k - oneCount >= 0) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - zeroCount][k - oneCount] + 1);
                    }
                }
            }
        }
        return dp[m][n];
    }
    public int[] count(String str) {
        int zeroCount = 0;
        int oneCount = 0;
        for(char ch: str.toCharArray()) {
            if (ch == '0') {
                zeroCount++;
            }
            if (ch == '1') {
                oneCount++;
            }
        }
        return new int[]{zeroCount, oneCount};
    }

    /**
     * 组合总和
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        // dp[i]: 和为 i 的组合个数
        int[] dp = new int[target + 1];
        // 初始化
        dp[0] = 1;
        for(int i = 1; i <= target; i++) {
            for(int x: nums) {
                if (i - x >= 0) {
                    dp[i] += dp[i - x];
                }
            }
        }
        return dp[target];
    }
}